package com.code.test.second.backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 * https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0046.%E5%85%A8%E6%8E%92%E5%88%97.md
 * <p>
 * <p>
 * 46.全排列
 * 力扣题目链接
 * <p>
 * 给定一个 没有重复 数字的序列，返回其所有可能的全排列。
 * <p>
 * 示例:
 * <p>
 * 输入: [1,2,3]
 * 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
 */
public class SCode46 {


    public static void main(String[] args) {
        int[] nums = {1,2,3};
        List<List<Integer>> ret = combine(nums);
        System.out.println(ret.size());
        System.out.println(ret);
    }


    static List<List<Integer>> ret = new ArrayList<>();
    //每个组合
    static List<Integer> temp = new ArrayList<>();

    static boolean[] used;

    public static List<List<Integer>> combine(int[] nums) {
        used = new boolean[nums.length];
        backtracking(nums);
        return ret;
    }


    public static void backtracking(int[] nums) {
        if (temp.size() == nums.length) {
            ret.add(new ArrayList<>(temp));
            return;
        }

        /**
         * 找到当前数字所对应的字母
         */
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }
            int cur = nums[i];
            temp.add(cur);
            used[i] = true;
            backtracking(nums);
            used[i] = false;
            temp.remove(temp.size() - 1);
        }

    }


}
